package my.algorithm.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 给定一些 points 和一个 origin，从 points 中找到 k 个离 origin 最近的点。按照距离由小到大返回。如果两个点有相同距离，则按照x值来排序；若x值也相同，就再按照y值排序。
 * 给出 points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
       返回 [[1,1],[2,5],[4,4]]
 * @author xsw
 * @date 2017-8-4
 */
public class closeK {
	public static void main(String[] args) {
		closeK main = new closeK();
		Point[] points = new Point[5];
		points[0] = new Point(4, 6);
		points[1] = new Point(4, 7);
		points[2] = new Point(4, 4);
		points[3] = new Point(2, 5);
		points[4] = new Point(1, 1);
		Point origin = new Point(0, 0);
		Point[] kClosest = main.kClosest(points, origin, 3);
		System.out.println(Arrays.toString(kClosest));
	}
	public Point[] kClosest(Point[] points, Point origin, int k) {
		Node parentNode = null;
		for(int i=0;i<points.length;i++){
			int distance = getDistance(points[i], origin);
			Node node = new Node(distance, points[i]);
			if(parentNode==null){
				parentNode=node;
				continue;
			}
			addNode(parentNode, node);
		}
		Point[] top = getTop(parentNode, k);
		return top;
    }
	public Point[] getTop(Node parentNode,int k){
		ArrayList<Point> list = new ArrayList<Point>();
		toList(parentNode, list);
		Point[] points =new Point[k];
		for (int i = 0; i < points.length; i++) {
			points[i]=list.get(i);
		}
		return points;
	}
	public void toList(Node parentNode,List<Point> list){
		if(parentNode==null)
			return ;
		toList(parentNode.leftNode, list);
		list.add(parentNode.point);
		toList(parentNode.rigthNode, list);
	}
	public void addNode(Node parentNode,Node node){
		Node nextNode = null;
		boolean isLeft = false;
		if(node.distance<parentNode.distance){
			nextNode = parentNode.leftNode;
			isLeft = true;
		}else if(node.distance>parentNode.distance){
			nextNode = parentNode.rigthNode;
			isLeft = false;
		}else{
			Point p1 = parentNode.point;
			Point p2 = node.point;
			if(p1.x>p2.x){
				nextNode = parentNode.leftNode;
				isLeft = true;
			}else if(p1.x==p2.x){
				if(p1.y>p2.y){
					nextNode = parentNode.leftNode;
					isLeft = true;
				}else{
					nextNode = parentNode.rigthNode;
					isLeft = false;
				}
			}else{
				nextNode = parentNode.rigthNode;
				isLeft = false;
			}
		}
		if(nextNode==null&&isLeft){
			parentNode.leftNode = node;
			return ;
		}
		if(nextNode==null&&!isLeft){
			parentNode.rigthNode = node;
			return ;
		}
		addNode(nextNode, node);
	}
	public int getDistance(Point p1,Point p2){
		int x = p1.x -p2.x;
		int y = p1.y - p2.y;
		return x*x+y*y;
	}
	class Node{
		int distance;
		Point point;
		Node leftNode;
		Node rigthNode;
		public Node(){}
		public Node(int distance,Point point){
			this.distance=distance;
			this.point=point;
		}
		public Node getLeftNode() {
			return leftNode;
		}
		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}
		public Node getRigthNode() {
			return rigthNode;
		}
		public void setRigthNode(Node rigthNode) {
			this.rigthNode = rigthNode;
		}
	}
	
}
class Point{
	int x;
	int y;
	Point(){x=0;y=0;}
	Point(int x,int y){
		this.x=x;
		this.y=y;
	}
	@Override
	public String toString() {
		return "[" + x + ", " + y + "]";
	}
}
